import codeJamUtils

def _build_board(case):
    numRows, numCols, numMines = case
    freeSpaces = numCols * numRows - numMines
    board = []
    doTransposeResult = False

    # for convenience make sure the board is either square or wider than it is tall
    if numRows > numCols:
        numCols, numRows = numRows, numCols
        doTransposeResult = True

    if numRows * numCols == numMines + 1:
        # edge case - there is only one free spot on the board
        board = [['*' for _ in range(numCols)] for _ in range(numRows)]
        board[0][0] = 'c'
    elif numRows == 1 and numCols >= numMines + 2:
        # if there is only one row, the problem is trivially solvable
        board.append((['*'] * numMines) + (['.'] * ((numCols - numMines) - 1)) + ['c'])
    elif numRows == 2:
        if freeSpaces > 3 and freeSpaces % 2 == 0:
            # A two row board is only solvable if there are > 3 free spaces and the number of free
            # spaces is even
            freeCols = freeSpaces // 2
            board.append(['c'] + ['.' for _ in range(freeCols - 1)] + ['*' for _ in range(numCols - freeCols)])
            board.append(['.' for _ in range(freeCols)] + ['*' for _ in range(numCols - freeCols)])
    elif freeSpaces >= 4 and freeSpaces != 5 and freeSpaces != 7:
        # in the general case, we will arrange the board in an 'L" pattern like this:
        # c.......
        # ........
        # ..******
        # ..******
        # ..******
        # ..******
        
        # Or this
        
        # c....***
        # .....***
        # ..******
        # ..******
        # ********
        # ********

        # fill with mines to start out
        board = [['*' for _ in range(numCols)] for _ in range(numRows)]

        # due to earlier condition checks, there must be at least 4 open spaces
        board[0][1] = board[1][0] = board[1][1] = '.'
        # set the click location
        board[0][0] = 'c'
        freeSpaces -= 4

        add1At = (2,2)
        add2VertAt = 2 
        add2HorAt = 2
        doAddOnes = False
        
        while freeSpaces > 0:
           
            if freeSpaces == 1:
                doAddOnes = True

            if not doAddOnes:
                if add2VertAt < numCols and (add2VertAt <= add2HorAt or add2HorAt >= numRows):
                    board[0][add2VertAt] = '.'
                    board[1][add2VertAt] = '.'
                    freeSpaces -= 2
                    add2VertAt += 1
                elif add2HorAt < numRows and (add2HorAt < add2VertAt or add2VertAt >= numCols):
                    board[add2HorAt][0] = '.' 
                    board[add2HorAt][1] = '.'
                    freeSpaces -= 2
                    add2HorAt += 1 
                else:
                    # we've filled the "L." Now we can just fill one at a
                    # time starting at the elbow
                    doAddOnes = True
            else:
                board[add1At[0]][add1At[1]] = '.'
                freeSpaces -= 1
                if add1At[1] == numCols - 1:
                    # wrap to next row
                    add1At = (add1At[0] + 1, 2)
                else:
                    add1At = (add1At[0], add1At[1] + 1)

    if doTransposeResult:
        board = list(zip(*board))
    return board

def _board2str(board):
    output = ""
    for row in board:
        for character in row:
           output += character
        output += "\n"
    return str.strip(output)

def _parse_input(inputLines):
    numCases = int(inputLines[0])
    cases = []
    for line in inputLines[1:]:
        numRows, numCols, numMines = str.split(line)
        cases.append((int(numRows), int(numCols), int(numMines)))
    return cases

if __name__ == "__main__":
    inputLines = codeJamUtils.get_input_lines("minesweeperMaster.txt")
    cases = _parse_input(inputLines)
    for i, case in enumerate(cases):
        solution = _build_board(case)
        if (len(solution) == 0):
            codeJamUtils.write_output("minesweeperMaster.txt", i+1, "\nImpossible")
        else:
            codeJamUtils.write_output("minesweeperMaster.txt", i+1, "\n" + _board2str(solution))

    fileIn.close()
    fileOut.close()

# You want to win the game as quickly as possible. There is nothing quicker than 
# winning in one click. Given the size of the board (R x C) and the number of 
# hidden mines M, is it possible (however unlikely) to win in one click? You 
# may choose where you click. If it is possible, then print any valid mine 
# configuration and the coordinates of your click